/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package clustering;


import java.util.Enumeration;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.logging.Level;
import java.util.logging.Logger;
import lucene.Analyzers.AnalyzerUtils;
import org.apache.lucene.index.TermFreqVector;

public class Kmeans2 extends ClusteringAlgorithm{
    
    final int MAX_ITERATIONS = 20;
    final int SEM_CLUSTER = -1;    
    
    private TermFreqVector[] termVectors;
    private int numVectors;
    private int[] clusterAtualDosVetores;
    private double[][] distanciaAtualDosVetores;
    private Hashtable<Integer, Integer> membrosCluster1; //soh a key importa
    private Hashtable<Integer, Integer> membrosCluster2;
    private Hashtable center1;
    private Hashtable center2;
    private LinkedList<String> searchTerms;    
    private int tipoDistancia;
    
    public Hashtable<String, Integer> popTermsClusterTop1;
    public Hashtable<String, Integer> popTermsClusterTop2;
    private Hashtable<Integer, Integer> clusterTop1, clusterTop2;
    
    public Kmeans2(TermFreqVector[] vectors, int nVectors, LinkedList<String> searchTerms){
        this.searchTerms = searchTerms;
        this.numVectors = nVectors;
        this.termVectors = vectors;
        this.center1 = new Hashtable<String,Double>();
        this.center2 = new Hashtable<String,Double>();
        clusterAtualDosVetores = new int[numVectors];
        membrosCluster1 = new Hashtable<Integer, Integer> ();
        membrosCluster2 = new Hashtable<Integer, Integer> ();
        distanciaAtualDosVetores = new double[numVectors][2]; 
    }

    public void run(int tipoDistancia, int topQuantos){
 
        this.tipoDistancia = tipoDistancia; 
        postMessage("K-Means clustering started");      
        
        try {   
            if(tipoDistancia == Kmeans2.DISTANCIA_COSSENO){
                initCenters(ClusteringAlgorithm.MAX_DIST_Cosseno);
                computeDistances_cosseno();           
            }  
            else if(tipoDistancia == Kmeans2.DISTANCIA_TANIMOTO){
                initCenters(ClusteringAlgorithm.MAX_DIST_Tanimoto);
                computeDistances_tanimoto();
            }
            makeAssignments();// Make the initial cluster assignments.

            int moves = 0, it = 0;
            do {
                computeCenters();// Compute the centers of the clusters that need updating.                
                if(tipoDistancia == Kmeans2.DISTANCIA_COSSENO)
                    computeDistances_cosseno();                     
                else if(tipoDistancia == Kmeans2.DISTANCIA_TANIMOTO)
                    computeDistances_tanimoto();
                moves = makeAssignments(); // Make this iteration's assignments
                it++;
                postMessage("... iteration " + it + " moves = " + moves);                
             } while (moves > 0 && it < MAX_ITERATIONS);

            printClusters();
            computePopularWords(topQuantos);  
            System.gc();
            
        } catch (ClassNotFoundException ex) {
            Logger.getLogger(Kmeans2.class.getName()).log(Level.SEVERE, null, ex);
      }
    }        
      
    private void initCenters(double maxDistance) throws ClassNotFoundException{
        int nCenter1 = -1, nCenter2 = -1;
        do{
            nCenter1 = (int) Math.round((numVectors-1) * Math.random());
            nCenter2 = (int) Math.round((numVectors-1) * Math.random());
        }while(nCenter1 == nCenter2);
        
        //inicializa vetor de distacancias e de clusters por termVector
        for (int i = 0; i < numVectors; i++){
            distanciaAtualDosVetores[i][0]=maxDistance;
            distanciaAtualDosVetores[i][1]=maxDistance;
            clusterAtualDosVetores[i]= SEM_CLUSTER;
        }
        
        //cada cluster ira conter somente o centro original
        includeInCluster(nCenter1, 1);
        this.clusterAtualDosVetores[nCenter1] = 1;
        postMessage("centro 1 escolhido = " + nCenter1);
        includeInCluster(nCenter2, 2);
        this.clusterAtualDosVetores[nCenter2] = 2;
        postMessage("centro 2 escolhido = " + nCenter2); 
        //sera computado o centro de cada cluster, mas que agora so contem o centro
        computeCenters();
    }    
    
    public void postMessage(String s){
        System.out.print("\n-->Kmeans algo: "+s);
    }
    
    private void printCenters(){
        postMessage("Center 1:");        
        String key;
        
        Enumeration keys = center1.keys();
        for (int i = 0; i < center1.size(); i++){
            key = (String) keys.nextElement();
            postMessage("-->" + i + ") Term: " + key +
                    " Frequency: "+  center1.get(key));
        }
        
        postMessage("Center 2:");     
        keys = center2.keys();
        for (int i = 0; i < center2.size(); i++){
            key = (String) keys.nextElement();
            postMessage("-->" + i + ") Term: " + key +
                    " Frequency: "+  center2.get(key));
        }
    }
    
    private void computeCenters() throws ClassNotFoundException{
        center1.clear();
        center2.clear();
        Hashtable <String,Integer> numeradores = new Hashtable<String, Integer>();
        int numTermVector;
        String term;
        double mean;
        Integer freqInInt, numerador;
        Enumeration<Integer> enumOfMembers;
        
        //para cada vetor do 1o cluster
        enumOfMembers = membrosCluster1.keys();
        while (enumOfMembers.hasMoreElements()){ 
            numTermVector = enumOfMembers.nextElement();
            
            //para cada termo no vetor
            for (int j = 0; j < termVectors[numTermVector].size(); j++){                
                term = termVectors[numTermVector].getTerms()[j];
                //se center ja tem o termo, pegar numerador anterior
                if (center1.containsKey(term))
                    numerador = (Integer) numeradores.get(term);   
                else
                    numerador = 0; 
                         
                freqInInt = termVectors[numTermVector].getTermFrequencies()[j];
                numerador = numerador + freqInInt;
                numeradores.put(term, numerador);
                mean = Double.valueOf(numerador.toString()) / membrosCluster1.size();
                center1.put(term, mean);
            }    
        }
        
        //para cada vetor do 2o cluster
        enumOfMembers = membrosCluster2.keys();
        while (enumOfMembers.hasMoreElements()){ 
            numTermVector = enumOfMembers.nextElement();
            
            //para cada termo no vetor
            for (int j = 0; j < termVectors[numTermVector].size(); j++){                
                term = termVectors[numTermVector].getTerms()[j];
                //se center ja tem o termo, pegar numerador anterior
                if (center2.containsKey(term))
                    numerador = (Integer) numeradores.get(term);   
                else
                    numerador = 0; 
                         
                freqInInt = termVectors[numTermVector].getTermFrequencies()[j];
                numerador = numerador + freqInInt;
                numeradores.put(term, numerador);
                mean = Double.valueOf(numerador.toString()) / membrosCluster2.size();
                center2.put(term, mean);
            }    
        }
                 
    }    
       
    public Enumeration<String> getListPopWordsCluster(int nCluster){
        Enumeration <String> e;
        if (nCluster == 1)
            e = this.popTermsClusterTop1.keys();
        else
            e = this.popTermsClusterTop2.keys();
        return e;
    }
    
    public void computePopularWords(int topQuantos){
        
        clusterTop1 = this.membrosCluster1;
        clusterTop2 = this.membrosCluster1;
        
        //computa a ordem dos centros
        if( this.membrosCluster2.size() > this.membrosCluster1.size()) //se 2 maior que 1
            clusterTop1 = this.membrosCluster2; //top1 = 2 e top2 = 1
        else
            clusterTop2 = this.membrosCluster2; //top1 = 1 e top2 = 2             
        
        this.postMessage("Size top1 Cluster = " + clusterTop1.size());
        this.postMessage("Size top2 Cluster = " + clusterTop2.size());
        
        this.popTermsClusterTop1 = computePopularWordsOfCluster(clusterTop1,topQuantos);
        this.popTermsClusterTop2 = computePopularWordsOfCluster(clusterTop2,topQuantos);
        
        this.printPopularWords();        
    }
        
   /* public Hashtable<String, Integer> computePopularWordsOfCluster(
            Hashtable<Integer, Integer> cluster, int topQuantos){
        
        Hashtable<String, Integer> termFreqTable = new Hashtable<String, Integer>();
        Enumeration<Integer> docs = cluster.keys();
        int doc, i=0, j=0, freq;
        String term;

         //coloca todos os termos em uma hashtable
        while(docs.hasMoreElements()){
            doc = docs.nextElement();
            for (j=0; j< this.termVectors[i].size(); j++){
                freq = 0;
                term = this.termVectors[i].getTerms()[j];
                if (!isASearchTerm(term) && !isHashtag(term)){
                    if (termFreqTable.containsKey(term)){
                        freq = termFreqTable.get(term);
                    }
                    termFreqTable.put(term, freq + 1);
                }
            }
            i++;
        }     
        
        //procura por termos com freq entre as top N;
        Enumeration<String> keyEnum = termFreqTable.keys();        
        Hashtable<String,Integer> popTermsTable = new Hashtable<String,Integer>();
        String key;
        
        int auxFreq = -1, topFreq;
        for (int t = 0; t < topQuantos; t++){  
            topFreq = getMaxFreqEnum(termFreqTable, auxFreq); 
            keyEnum = termFreqTable.keys(); 
            while (keyEnum.hasMoreElements()){
                key = keyEnum.nextElement();
                if( (Integer)termFreqTable.get(key) == topFreq)
                    popTermsTable.put(key,topFreq);
            }
            auxFreq = topFreq;            
        }  
        
        return popTermsTable;
    }*/
    
    public Hashtable<String, Integer> computePopularWordsOfCluster(
            Hashtable<Integer, Integer> cluster, int topQuantos){
        
        Hashtable<String, Integer> termFreqTable = new Hashtable<String, Integer>();
        Enumeration<Integer> vectorsOfCluster = cluster.keys();
        int vector, j=0, freq;
        String term;

         //coloca todos os termos em uma hashtable
        while(vectorsOfCluster.hasMoreElements()){
            vector = vectorsOfCluster.nextElement();
            for (j=0; j< this.termVectors[vector].size(); j++){
                freq = 0;
                term = this.termVectors[vector].getTerms()[j];
                if (!isASearchTerm(term) && !isHashtag(term)){
                    if (termFreqTable.containsKey(term)){
                        freq = termFreqTable.get(term);
                    }
                    termFreqTable.put(term, freq + 1);
                }
            }
        }     
        
        //procura por termos com freq entre as top N;
        Enumeration<String> termsOfCluster;       
        Hashtable<String,Integer> popTermsTable = new Hashtable<String,Integer>();      
              
        int auxFreq = -1, topFreq;
        for (int t = 0; t < topQuantos; t++){  
            topFreq = getMaxFreqEnum(termFreqTable, auxFreq);
            termsOfCluster = termFreqTable.keys();
            while (termsOfCluster.hasMoreElements()){
                term = termsOfCluster.nextElement();
                if( (Integer)termFreqTable.get(term) == topFreq)
                    popTermsTable.put(term,topFreq);
            }
            auxFreq = topFreq;            
        } 
        
        return popTermsTable;
    }
        
    private int getMaxFreqEnum(Hashtable<String,Integer> termFreqTable, int teto){
        int top = 0, aux;
        Enumeration<Integer> freqEnum = termFreqTable.elements();
        while(freqEnum.hasMoreElements()){
            aux = freqEnum.nextElement();
            if ( aux > top && (aux < teto || teto == -1))
                top = aux;
        }
        return top;
    }
    
    public void printPopularWords(){
        Enumeration <String> topTerms; int i;
        String term;
                
        topTerms = this.popTermsClusterTop1.keys(); i = 0;
        this.postMessage("\n *** Pop Words Center 1 ***");
        while(topTerms.hasMoreElements()){
            term = topTerms.nextElement();
            this.postMessage(i + ") Term: " + term + " Freq: " + 
                    this.popTermsClusterTop1.get(term));
        }
        
        topTerms = this.popTermsClusterTop2.keys(); i = 0;
        this.postMessage("\n *** Pop Words Center 2 ***");
        while(topTerms.hasMoreElements()){
            term = topTerms.nextElement();
            this.postMessage(i + ") Term: " + term + " Freq: " + 
                    this.popTermsClusterTop2.get(term));
        }
    }
    
    public boolean isASearchTerm(String s){
        for (int i = 0; i< this.searchTerms.size(); i++){
            if (s.equalsIgnoreCase(searchTerms.get(i)))      
                 return true;
        }
        return false;
    }
    
    public boolean isHashtag(String s){
        return s.startsWith("#");
    }   
     
    private void computeDistances_cosseno(){
        double distance; 
        for (int i = 0; i < termVectors.length; i++){  
            distance = calculateDistance_cosseno(termVectors[i], center1);
            distanciaAtualDosVetores[i][0] = distance;
            distance = calculateDistance_cosseno(termVectors[i], center2);
            distanciaAtualDosVetores[i][1] = distance; 
            System.out.println(" ----- DOC " + i + "  to1: " + distanciaAtualDosVetores[i][0] +
                    "  to2: " + distanciaAtualDosVetores[i][1] );
        }
    }   
   
          
    private void computeDistances_tanimoto(){
        double distance;
        for (int i = 0; i < termVectors.length; i++){ 
            distance = calculateDistance_tanimoto(termVectors[i], center1);
            distanciaAtualDosVetores[i][0] = distance;
            distance = calculateDistance_tanimoto(termVectors[i], center2);
            distanciaAtualDosVetores[i][1] = distance;
            System.out.println(" ----- DOC " + i + "  to1: " + distanciaAtualDosVetores[i][0] +
                    "  to2: " + distanciaAtualDosVetores[i][1] );
        }
    }
    
    private int makeAssignments(){
        int moves = 0, clusterOriginal, novoCluster;
        for (int i = 0; i < termVectors.length; i++){
            clusterOriginal = this.clusterAtualDosVetores[i];
            if (this.distanciaAtualDosVetores[i][0]<this.distanciaAtualDosVetores[i][1])
                novoCluster = 1;
            else
                novoCluster = 2;
            if(clusterOriginal != novoCluster){
                moves = moves + 1;
                clusterAtualDosVetores[i] = novoCluster;
                includeInCluster(i,novoCluster);
                if (clusterOriginal != SEM_CLUSTER)
                    excludeFromCluster(i,clusterOriginal);                
            }
        }
        //printClusters3();
        return moves;
    }
    
    public void printClusters(){       
        Enumeration<Integer> enumOfMembers; 
        int i, member;
                
        this.postMessage("**** CLuster 1*****");
        enumOfMembers = membrosCluster1.keys();
        i = 1;
        while (enumOfMembers.hasMoreElements()){
            member = enumOfMembers.nextElement();
            this.postMessage(i+ ") " + member);
            AnalyzerUtils.displayTermVector(this.termVectors[member]); 
            i++;
        }
        
        this.postMessage("**** CLuster 2*****");
        enumOfMembers = membrosCluster2.keys();
        i = 1;
        while (enumOfMembers.hasMoreElements()){
            member = enumOfMembers.nextElement();
            this.postMessage(i+ ") " + member);
            AnalyzerUtils.displayTermVector(this.termVectors[member]); 
            i++;
        }        
    }
    
    private void includeInCluster(int i, int cluster){
        switch(cluster){
            case 1: this.membrosCluster1.put(i, 0); 
                    break;
            case 2: this.membrosCluster2.put(i, 0);  break;
        }
    }
    
    private void excludeFromCluster(int i, int cluster){
        switch(cluster){
            case 1: this.membrosCluster1.remove(i); break; 
            case 2: this.membrosCluster2.remove(i); break;
        }
    }   

    private double calculateDistance_cosseno(TermFreqVector tv1, Hashtable center){
        double nominator = 0, denominatorA = 0, denominatorB = 0, denominator = 0;
        double x1, x2;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i];
            if(!this.isASearchTerm(key)){
                x1 = 0;            
                x1 = tv1.getTermFrequencies()[i];            
                if (center.containsKey(key)) //se tem nos dois.....
                    nominator = nominator + x1* ((Double) center.get(key)); // somatoria Ai ^ Bi
                denominatorA = denominatorA + Math.pow(x1, 2);   // somatoria Ai ^2  
            }
        }
        
        //depois checa todos os termos de center        
        Enumeration keyEnum = center.keys();
        while(keyEnum.hasMoreElements()){  
            key = (String) keyEnum.nextElement();
            if(!this.isASearchTerm(key)){
                x2 = (Double) center.get(key);
                denominatorB = denominatorB + Math.pow(x2, 2);   //somatoria Bi ^2   
            }
        }
        
        denominator = Math.sqrt(denominatorA) * Math.sqrt(denominatorB);
        return 1 - nominator / denominator;  
        //se cos = 0 entao 90 graus, mais distante possivel (distancia 1)
        // se cos = 1 entao é o mesmo vetor, mas proximo possivel (distancia 0)
                                            
    }
    
    private double calculateDistance_tanimoto(TermFreqVector tv1, Hashtable center){
        double vectorDotCenter = 0, modVector = 0, modCenter = 0;
        double freqNoCentro;
        Integer freqNoVetor;
        Double freqNoVetorDouble;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i];   
            if(!this.isASearchTerm(key)){
                freqNoVetor = tv1.getTermFrequencies()[i];
                freqNoVetorDouble = Double.valueOf(freqNoVetor.toString());
                if (center.containsKey(key)){ //se tem nos dois.....
                    freqNoCentro = (Double) center.get(key);
                    vectorDotCenter = vectorDotCenter + freqNoCentro * freqNoVetor;
                }   
                modVector = modVector + Math.pow(freqNoVetorDouble, 2);  
            }
        }        
        
        //depois checa todos os termos de center
        Enumeration keyEnum = center.keys();
        while(keyEnum.hasMoreElements()){  //## Checa se eh assim que usa enumeration
            key = (String) keyEnum.nextElement();
            if(!this.isASearchTerm(key)){
                freqNoCentro = (Double) center.get(key);
                modCenter = modCenter + Math.pow(freqNoCentro, 2); 
            }
        }        
        return (1 - (vectorDotCenter / (modVector + modCenter - vectorDotCenter)));                                              
    }
    
    //nao deve ser usada
    private double calculateDistance_alternativa(TermFreqVector tv1, Hashtable center){
        double denominador = 1;
        int numIntv2;
        String key;
        
        //checa todos os termos de tv1
        for (int i = 0; i< tv1.size(); i++){
            key = tv1.getTerms()[i];     
            if (!this.isASearchTerm(key)) {               
                if (center.containsKey(key)){ //se tem nos dois.....                    
                    denominador = denominador * 2;       
                    if (this.isHashtag(key));
                        denominador = denominador * 2;    
                }  
            }
        }
        return 1/denominador;
    }
    
    @Override
    public int[] getSizeTopClusters() {
        int[] size = new int[2];
        size[0] = this.clusterTop1.size();
        size[1] = this.clusterTop2.size();
        return size;
    }

}


